package main

import (
	"fmt"
	"math"
)

/*
最大子序和

给定一个整数数组 nums ，
找到一个具有最大和的连续子数组（子数组最少包含一个元素），
返回其最大和。
*/
func main() {
	nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
	fmt.Println(maxSubArray(nums))
}

/*
f(i) 表示在下标为i处，它的最大子序和
状态转移方程 f(i) = max { num[i], f(i-1) + num[i] }
*/
func maxSubArray(nums []int) int {
	max := nums[0]
	// 时间复杂度和空间复杂度都是O(n)
	for i := 1; i < len(nums); i++ {
		// 如果加上当前数字会使子序和增加
		nums[i] = int(math.Max(float64(nums[i]+nums[i-1]), float64(nums[i])))
		if max < nums[i] {
			max = nums[i]
		}
	}
	return max
}
